package com.adaydayup.week3;

import java.util.ArrayDeque;

/*
1823. 找出游戏的获胜者

 */
public class FindTheWinner1823 {
    //数学+递归
    public int findTheWinner(int n, int k) {
        if (n == 1) return 1;
        return (k + findTheWinner(n - 1, k) - 1) % n + 1;
    }

    //模拟+队列
    /*
    offer(E e) 在此deque的末尾插入指定的元素。
    peek()     检索但不删除由此deque表示的队列的头部，如果此deque为空，则返回 null 。
    poll()     检索并删除由此deque（换句话说，该deque的第一个元素）表示的队列的 null如果此deque为空，则返回 null 。

    将队首元素取出并将该元素在队尾处重新加入队列，
    重复该操作 k - 1k−1 次，则在 k - 1k−1 次操作之后，
    队首元素即为这一轮中数到的第 kk 名小伙伴的编号，将队首元素取出，即为数到的第 kk 名小伙伴离开圈子。
    上述操作之后，新的队首元素即为下一轮游戏的起始小伙伴的编号。

     */
    public int findTheWinner2(int n,int k){
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        for (int i = 1; i <=n; i++) {
            queue.offer(i);
        }
        while (queue.size()>1){
            //注意是 i < k
            for (int i = 1; i < k; i++) {
                //取出队首元素追加到队尾
                queue.offer(queue.poll());
            }
            queue.poll();//删除队首
        }
        return queue.peek();
    }

    public static void main(String[] args) {
        FindTheWinner1823 find = new FindTheWinner1823();
        int theWinner = find.findTheWinner2(6, 5);
        System.out.println(theWinner);
    }
}
